package com.tsx.leetcode.hot100.medium;

/**
 * <a href="https://leetcode.cn/problems/container-with-most-water">盛最多的水</a>
 */
public class Q11MaxArea {
    public static void main(String[] args) {
        int[] height = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
        Q11MaxArea q11MaxArea = new Q11MaxArea();
        int max = q11MaxArea.maxArea(height);
        System.out.println("max = " + max);
    }

    /**
     * 解题思路
     * 双指针法：使用两个指针，一个指向数组的起始位置（left），另一个指向数组的末尾位置（right）。
     * 计算面积：计算当前两个指针所指向的线段与x轴构成的容器的面积，面积由较短的那条线的高度和两个指针之间的距离决定。
     * 移动指针：为了寻找可能更大的面积，移动较短的那条线的指针向内侧移动一位，因为移动较长的线的指针不会增加容器的高度，而移动较短的线的指针有可能找到更高的线，从而增加面积。
     * 更新最大面积：在每次移动指针后，计算新的面积，并更新最大面积。
     * 重复步骤：重复上述过程，直到两个指针相遇。
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int length = height.length;
        int left = 0;
        int right = length - 1;
        int maxArea = 0;
        while (left < right) {
            int minHeight = Math.min(height[left], height[right]);
            int area = minHeight * (right - left);
            if (area > maxArea) {
                maxArea = area;
            }
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}
